﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

namespace TestXNA3
{
    // Taken from http://www.comp.nus.edu.sg/~tants/shadow-x/download.htm
    //class MathHelper2D
    //{
        static class TransformHelper
        {
            public static Vector2 DeviceToScreen(Vector2 device, float viewportWidth, float viewportHeight)
            {
                return new Vector2((device.X + 1.0f) * 0.5f * viewportWidth, (device.Y + 1.0f) * 0.5f * viewportHeight);
            }
        }

        static class MathHelper2D
        {
            public static bool RayIntersect(out Vector2 i, Ray2D l1, Ray2D l2)
            {
                float denominator = l1.Direction.X * l2.Direction.Y - l1.Direction.Y * l2.Direction.X;
                if (Math.Abs(denominator) < Single.Epsilon)
                {
                    i = Vector2.Zero;
                    return false;
                }

                float numerator = l1.Direction.Y * (l2.Position.X - l1.Position.X) - l1.Direction.X * (l2.Position.Y - l1.Position.Y);
                float t = numerator / denominator;

                i = l2.Position + t * l2.Direction;

                return true;
            }

            public static float CounterClockwise(Vector2 p, Vector2 q, Vector2 r)
            {
                return (q.X - p.X) * (r.Y - p.Y) - (r.X - p.X) * (q.Y - p.Y);
            }

            public static float CalcTriangleArea(Vector2 p, Vector2 q, Vector2 r)
            {
                return 0.5f * CounterClockwise(p, q, r);
            }

            public static float Determinant(float a, float b, float c, float d)
            {
                return a * d - b * c;
            }
        }

        class ConvexHull2D
        {
            public Vector2[] vertices;

            public ConvexHull2D(Vector2[] points)
            {
                Construct(points);
            }

            public void Construct(Vector2[] pts)
            {
                // Copy to points
                Vector2[] points = (Vector2[])pts.Clone();

                // select lowest right most point p in points
                int lowestRightMost = 0;
                for (int i = 1; i < points.Length; ++i)
                    if (points[i].Y < points[lowestRightMost].Y ||
                        (Math.Abs(points[i].Y - points[lowestRightMost].Y) < Single.Epsilon && points[i].X > points[lowestRightMost].X))
                        lowestRightMost = i;

                // sort points from small angle to big angle
                // i.e. from big cos to small cost
                Vector2 temp = Vector2.Zero;
                Vector2 pivot = points[lowestRightMost];

                // swap 0 and lowestRightMost
                temp = points[0];
                points[0] = points[lowestRightMost];
                points[lowestRightMost] = temp;
                for (int i = 1; i < points.Length - 1; ++i)
                {
                    int maxCosThetaIndex = i;

                    Vector2 v = points[i] - pivot;
                    float cosTheta = Vector2.Dot(Vector2.UnitX, v) / v.Length();
                    for (int j = i + 1; j < points.Length; ++j)
                    {
                        Vector2 v2 = points[j] - pivot;
                        float cosTheta2 = Vector2.Dot(Vector2.UnitX, v2) / v2.Length();
                        if (cosTheta2 > cosTheta)
                        {
                            cosTheta = cosTheta2;
                            maxCosThetaIndex = j;
                        }
                    }

                    if (maxCosThetaIndex != i)
                    {
                        // swap
                        temp = points[i];
                        points[i] = points[maxCosThetaIndex];
                        points[maxCosThetaIndex] = temp;
                    }
                }

                // Push points[0] and points[1] to the stack
                vertices = new Vector2[points.Length];
                vertices[0] = points[0];
                vertices[1] = points[1];
                int capacity = 2;

                int k = 2;
                while (k < points.Length)
                {
                    if (capacity < 2)
                        vertices[capacity++] = points[k++];
                    else
                    {
                        Vector2 top = vertices[capacity - 1];
                        Vector2 top2 = vertices[capacity - 2];

                        float ccwTest = MathHelper2D.CounterClockwise(top2, top, points[k]);
                        if (Math.Abs(ccwTest) < Single.Epsilon || ccwTest >= 0.0f)
                            vertices[capacity++] = points[k++];
                        else
                            --capacity;
                    }
                }

                System.Array.Resize<Vector2>(ref vertices, capacity);
            }

            public static float FindArea(Vector2[] points)
            {
                float area = 0.0f;
                for (int i = 1; i < points.Length - 1; ++i)
                    area += Math.Abs(MathHelper2D.CalcTriangleArea(points[0], points[i], points[i + 1]));
                return area;
            }
        };

        struct Ray2D
        {
            Vector2 position;
            Vector2 direction;

            // Properties
            public Vector2 Position { get { return position; } set { position = value; } }
            public Vector2 Direction { get { return direction; } set { direction = value; } }

            public Ray2D(Vector2 _position, Vector2 _direction)
            {
                position = _position;
                direction = _direction;
            }

            public float SignedDistanceFromPoint(Vector2 p)
            {
                return (direction.X * (position.Y - p.Y) - (position.X - p.X) * direction.Y) / direction.Length();
            }

            public Vector2 MaxPointToLine(Vector2[] points)
            {
                float maxDistance = 0.0f;
                int maxIndex = 0;

                int i;
                for (i = 0; i < points.Length; ++i)
                {
                    float dist = Math.Abs(SignedDistanceFromPoint(points[i]));
                    if (dist > maxDistance)
                    {
                        maxDistance = dist;
                        maxIndex = i;
                    }
                }

                return points[maxIndex];
            }

            public Ray2D Ortho()
            {
                return new Ray2D(position, new Vector2(-direction.Y, direction.X));
            }

            public Ray2D Parallel(Vector2 q)
            {
                return new Ray2D(q, direction);
            }
        }
    //}
}
